package com.shm.leetcode;

/**
 * 110. 平衡二叉树
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 *
 * 本题中，一棵高度平衡二叉树定义为：
 *
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 *
 * 示例 1:
 *
 * 给定二叉树 [3,9,20,null,null,15,7]
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回 true 。
 *
 * 示例 2:
 *
 * 给定二叉树 [1,2,2,3,3,null,null,4,4]
 *
 *        1
 *       / \
 *      2   2
 *     / \
 *    3   3
 *   / \
 *  4   4
 * 返回 false 。
 * @author SHM
 */
public class IsBalancedTree {
    /**
     * 前言
     * 这道题中的平衡二叉树的定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过 11，则二叉树是平衡二叉树。根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上。
     *
     * 方法一：自顶向下的递归
     * 定义函数 \texttt{height}height，用于计算二叉树中的任意一个节点 pp 的高度：
     *
     * \texttt{height}(p) = \begin{cases} 0 & p \text{ 是空节点}\\ \max(\texttt{height}(p.left), \texttt{height}(p.right))+1 & p \text{ 是非空节点} \end{cases}
     * height(p)={
     * 0
     * max(height(p.left),height(p.right))+1
     * ​
     *
     * p 是空节点
     * p 是非空节点
     * ​
     *
     *
     * 有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n ^ 2)O(n
     * 2
     *  )，其中 nn 是二叉树中的节点个数。
     * 最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)O(n)。
     * 对于节点 pp，如果它的高度是 dd，则 \texttt{height}(p)height(p) 最多会被调用 dd 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 hh 满足 O(h)=O(\log n)O(h)=O(logn)，因为 d \leq hd≤h，所以总时间复杂度为 O(n \log n)O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)O(n)，此时总时间复杂度为 O(n^2)O(n
     * 2
     *  )。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 nn。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return (Math.abs(height(root.left)-height(root.right))<2&&isBalanced(root.left)&&isBalanced(root.right));
    }

    public int height(TreeNode root){
        if(root == null){
            return 0;
        }else{
            return Math.max(height(root.left),height(root.right)) + 1;
        }
    }


    /**
     * 方法二：自底向上的递归
     * 方法一由于是自顶向下递归，因此对于同一个节点，函数 \texttt{height}height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 \texttt{height}height 只会被调用一次。
     *
     * 自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)O(n)。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 nn。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/
     * @param root
     * @return
     */
    public boolean isBalanced_2(TreeNode root) {
        return height_2(root) >= 0;
    }

    public int height_2(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = height_2(root.left);
        int rightHeight = height_2(root.right);
        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight-rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight,rightHeight) + 1;
    }
}
